package com.base.heap;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 1005. K 次取反后最大化的数组和
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 *
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 *
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年12月03日 20:53
 */
public class LargestSumAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add(num);
        }
        for (int i = 0; i < k; i++) {
            queue.add(-queue.poll());
        }
        Iterator<Integer> iterator = queue.iterator();
        int sum = 0;
        while (iterator.hasNext()){
            sum+=iterator.next();
        }
        return sum;
    }
}
